#include <stdio.h>
#include <stdlib.h>

//希尔排序
/*
不稳定，仅适用于顺序表，不适用于链表
先追求表中元素部分有序，在逐渐逼近全局有序
时间复杂度未知


希尔排序:先将待排序表分割成若干形如L[i,i+d,i+ 2....+ kd]的“特殊”子表，对各个子表
分别进行直接插入排序。缩小增量d

*/

//希尔排序
void ShellSort(int A[], int n)
{
    int d, i, j;
    // A[0]只是暂存单元，不是哨兵，当j<=0时， 插入位置已到
    for (d = n / 2; d >= 1; d = d / 2) //步长变化
        for (i = d + 1; i <= n; ++i)
            if (A[i] < A[i - d]) //需将A[i]插入有序增量子表
            {
                A[0] = A[i]; //暂存在A[0]
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d)
                {
                    A[j + d] = A[j]; // 记录后移，查找插入的位置
                }
                A[j + d] = A[0]; //插入.
            }                    // if
}

int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}